#include <stdio.h>
#include <stdlib.h>

/*
 * AOE : 带权DAG. 关键路径
 */

#define vertex 9
#define edge   11

struct link
{
  int data;
  int weight;
  struct link * next;
};

struct graph
{
  int ve[vertex+1], v1[vertex+1];
  int s1[100], s2[100];
  int top1, top2;
  struct link a[vertex+1];
};

void adjacency(struct graph * graph)
{
  int i, j, k, w;
  struct link * src;

  for (i = 1; i <= vertex; i++) {
    graph->a[i].data = 0;
    graph->a[i].next = NULL;
    graph->a[i].weight = 0;
  }

  for (k = 1; k <= edge; k++) {
    printf("input a edge:\n");
    scanf("%d %d %d", &i, &j, &w);

    src = (struct link *) malloc (sizeof(struct link));
    src->data = j;
    src->weight = w;
    src->next = graph->a[i].next;
    graph->a[i].next = src;
    graph->a[i].data++;
  }
}

void topsort(struct graph * graph)
{
  int j, k, m = 0;
  int i, x;
  struct link * src;

  graph->top1 = 0;
  graph->top2 = 0;

  for (x = 1; x <= vertex; x++)
    graph->ve[x] = 0;

  for (i = 1; i <= vertex; i++)
    if (graph->a[i].data == 0) {
      graph->top1++;
      graph->s1[graph->top1] = i;
    }

  while (graph->top1 > 0) {
    j = graph->s1[graph->top1--];
    graph->s2[++graph->top2] = j;
    m++;

    src = graph->a[j].next;
    while (src != NULL) {
      k = src->data;
      graph->a[k].data--;

      if (graph->a[k].data == 0)
	graph->s1[++graph->top1] = k;

      if (graph->ve[j] + src->weight > graph->ve[k])
	graph->ve[k] = graph->ve[j] + src->weight;

      src = src->next;
    }
  }
}

void critical_path(struct graph * graph)
{
  int j, k, kk, ee, el;
  struct link * src;
  int y;

  for (y = 1; y <= vertex; y++)
    graph->v1[y] = graph->ve[vertex];

  while (graph->top2 > 0) {
    j = graph->s2[graph->top2--];
    src = graph->a[j].next;

    while (src != NULL) {
      k = src->data;
      kk = src->weight;

      if (graph->v1[k] - kk < graph->v1[j])
	graph->v1[j] = graph->v1[k] - kk;

      src = src->next;
    }
  }

  printf(" critical path is : ");

  for (j = 1; j <= vertex; j++) {
    src = graph->a[j].next;
    
    while (src != NULL) {
      k = src->data;
      kk = src->weight;
      ee = graph->ve[j];
      el = graph->v1[k] - kk;

      if (ee == el)
	printf("vertex %d to vertex %d\n ", j, k);

      src = src->next;
    }
  }
  printf("\n");
}

void main()
{
  struct graph graph;

  adjacency(&graph);
  topsort(&graph);
  critical_path(&graph);
}


